/*
 * @lc app=leetcode.cn id=18 lang=golang
 * @lcpr version=30118
 *
 * [18] 四数之和
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start

type Node struct {
	I   int
	J   int
	Sum int
}

func fourSum(nums []int, target int) [][]int {

	if len(nums) < 4 {
		return nil
	}

	n := len(nums)
	m := n * (n - 1) / 2
	dp := make([]Node, m)
	{
		k := 0
		for i := 0; i < n; i++ {
			for j := i + 1; j < n; j++ {
				dp[k] = Node{I: i, J: j, Sum: nums[i] + nums[j]}
				k++
			}
		}
	}

	// fmt.Println(dp)

	// 按照 Node.Sum 对 dp 从小到大排序
	sort.Slice(dp, func(i, j int) bool {
		return dp[i].Sum < dp[j].Sum
	})

	res := make([][]int, 0)
	resSet := make(map[string]bool)
	for i := 0; i < m; i++ {
		tmp := binarySearch(dp, target-dp[i].Sum, i+1, m-1)
		if tmp != -1 {

			l, r := tmp-1, tmp+1
			for l > i && dp[l].Sum == dp[tmp].Sum {
				l--
			}
			for r < m && dp[r].Sum == dp[tmp].Sum {
				r++
			}

			for tmp = l + 1; tmp < r; tmp++ {
				result := []int{nums[dp[i].I], nums[dp[i].J], nums[dp[tmp].I], nums[dp[tmp].J]}
				sort.Ints(result)                            // 对结果进行排序，以便生成唯一的键
				resultKey := fmt.Sprintf("%v", result)       // 将结果转换为字符串，作为键
				if _, exists := resSet[resultKey]; !exists { // 如果这个键还不存在，那么就添加这个结果
					res = append(res, result)
					resSet[resultKey] = true
				}
			}
		}
	}
	return res
}

func binarySearch(nums []Node, target int, left int, right int) int {
	l, r := left, right
	for l <= r {
		mid := l + (r-l)/2
		if nums[mid].Sum < target {
			l = mid + 1
		} else if nums[mid].Sum > target {
			r = mid - 1
		} else {
			return mid
		}
	}
	return -1
}

// @lc code=end

/*
// @lcpr case=start
// [1,0,-1,0,-2,2]\n0\n
// @lcpr case=end

// @lcpr case=start
// [2,2,2,2,2]\n8\n
// @lcpr case=end

*/

